package com.coder.algorithm.search;

import java.util.Arrays;

/**
 * 二分查找
 * <p>
 * 当然如果不想使用 start <= end ,可以写成 start < end，然后在while外面在进行一次判断。
 *
 * @author yuhushuan
 * @date 2020/6/7 23:08
 */
public class BinarySearch implements Search {

    public BinarySearch() {
        System.out.println("二分查找");
    }


    /**
     * 二分查找
     *
     * @param array 不重复数组中
     * @param k     查找目标
     * @return 数组下标，不存在返回 -1
     */
    @Override
    public int search(int[] array, int k) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int start = 0;
        int end = array.length - 1;
        // 注意：这里有等于号，原因是当 start,end 被更新后，会出现 start==end 的情况，这时候可以退出循环了
        // 但是最后一步需要判断是否 array[start]==k,方法就是再进入一次循环；
        while (start <= end) {
            int middle = (start + end) >>> 1;// 防止溢出
            if (k == array[middle]) {
                return middle;
            } else if (k < array[middle]) {// 判断下限
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找
     *
     * @param array 不重复数组中
     * @param k     查找目标
     * @return 数组下标，不存在返回 -1
     */
    public int search_solution2(int[] array, int k) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int start = 0;
        int end = array.length - 1;
        // 注意：这里有等于号，原因是当 start,end 被更新后，会出现 start==end 的情况，这时候可以退出循环了
        // 但是最后一步需要判断是否 array[start]==k,方法就是再进入一次循环；
        while (start < end) {
            int middle = (start + end) >>> 1;// 防止溢出
            if (k == array[middle]) {
                return middle;
            } else if (k < array[middle]) {// 判断下限
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        if (array[start] == k) {
            return start;
        }
        return -1;
    }

    /**
     * 二分查找第一次出现(左边界)的位置
     *
     * @param array 有重复数字的数组
     * @param k     目标
     * @return 第一次出现(左边界)的位置
     */
    public static int searchFirst(int[] array, int k) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int start = 0;
        int end = array.length - 1;
        // 注意：这里有等于号，原因是当 start,end 被更新后，会出现 start==end 的情况，这时候可以退出循环了
        // 但是最后一步需要判断是否 array[start]==k,方法就是再进入一次循环；
        while (start < end) {
            int middle = (start + end) >>> 1;// 防止溢出

            // 当找到目标的时候，保持右侧 end指向target,然后 start 继续逼近 end,
            // 最终将 start 和 end 将在最左侧的target位置相遇
            // 当没有找到目标的时候，且 k < array[mid]，保持 end 指向更高的值。
            if (k == array[middle]) {
                end = middle;
            } else if (k < array[middle]) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        if (array[start] == k) {
            return start;
        }
        return -1;
    }

    /**
     * 二分查找最后一次出现(右边界)的位置
     *
     * @param array 有重复数字的数组
     * @param k     目标
     * @return 最后一次出现(右边界)的位置
     */
    public static int searchLast(int[] array, int k) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int start = 0;
        int end = array.length - 1;
        // 注意：这里有等于号，原因是当 start,end 被更新后，会出现 start==end 的情况，这时候可以退出循环了
        // 但是最后一步需要判断是否 array[start]==k,方法就是再进入一次循环；
        while (start < end) {
            int middle = (start + end + 1) >> 1;// 注意，这里取偏右的中值，【防止死循环】

            // 当找到目标的时候，保持左侧 start 指向 target,然后 end 继续逼近 start,
            // 最终将 start 和 end 将在最右侧的target位置相遇
            // 当没有找到目标的时候，且 k > array[mid]，保持 start 指向更低的值。
            if (k == array[middle]) {
                start = middle;
            } else if (k < array[middle]) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        if (array[start] == k) {
            return start;
        }
        return -1;
    }


    public static int getFirstK(int[] data, int k, int start, int end) {
        if (data == null || data.length == 0 || start > end) {
            return -1;
        }
        int middleIndex = (start + end) >> 1;
        int middleData = data[middleIndex];

        if (middleData == k) {
            if ((middleIndex > 0 && data[middleIndex - 1] < k)
                    || middleIndex == 0) {
                return middleIndex;
            } else {
                end = middleIndex - 1;
            }
        } else if (middleData > k) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
        return getFirstK(data, k, start, end);
    }

    public static int getLastK(int[] data, int k, int start, int end) {
        if (data == null || data.length == 0 || start > end) {
            return -1;
        }
        int middleIndex = (start + end) >> 1;
        int middleData = data[middleIndex];

        if (middleData == k) {
            if ((middleIndex < data.length - 1 && data[middleIndex + 1] > k)
                    || middleIndex == data.length - 1) {
                return middleIndex;
            } else {
                start = middleIndex + 1;
            }
        } else if (middleData > k) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
        return getLastK(data, k, start, end);
    }

    public static void main(String[] args) {
        print(new int[]{1, 2, 3, 3, 3, 4, 5}, 3);
        print(new int[]{1, 2, 3, 3, 3, 4, 5}, 1);
        print(new int[]{1, 2, 3, 3, 3, 4, 5}, 5);
    }

    private static void print(int[] array, int k) {
        System.out.println("数组：" + Arrays.toString(array));
        System.out.println("第一个值为 " + k + " 的下标为：" + searchFirst(array, k));
        System.out.println("最后一个值为 " + k + " 的下标为：" + searchLast(array, k));
        System.out.println();
    }
}
